# encoding=utf8

import math

"""
    给定一个长度为 n 的数组 nums ，元素按从小到大的顺序排列且不重复。
    请查找并返回元素 target 在该数组中的索引。若数组不包含该元素，则返回-1 
"""


def binary_search(nums, num):
    i, j = 0, len(nums)
    while i < j:
        m = math.trunc((i + j) / 2)  # 也可以直接用 (i+j)//2 直接获取计算结果的整数部分
        if nums[m] > num:
            j = m
        elif nums[m] < num:
            i = m + 1
        else:
            return m
    return -1


print(binary_search([1, 2, 3], 10000))


def binary_search_lcro(nums: list[int], target: int) -> int:
    """二分查找（左闭右开区间）"""
    # 初始化左闭右开区间 [0, n) ，即 i, j 分别指向数组首元素、尾元素+1
    i, j = 0, len(nums)
    # 循环，当搜索区间为空时跳出（当 i = j 时为空）
    while i < j:
        m = (i + j) // 2  # 计算中点索引 m
        if nums[m] < target:
            i = m + 1  # 此情况说明 target 在区间 [m+1, j) 中
        elif nums[m] > target:
            j = m  # 此情况说明 target 在区间 [i, m) 中
        else:
            return m  # 找到目标元素，返回其索引
    return -1  # 未找到目标元素，返回 -1


print(binary_search_lcro([1, 2, 3], 10000))
